\nonstopmode
\documentclass{beamer}

\mode<presentation>
{
\usetheme{sts}

\setbeamercovered{transparent}
}

%\documentclass[handout]{beamer}
%\includeonlylecture{week12}

\input{header.tex}

\usepackage{url}%
\urldef{\mailsa}\path|{felix.kurth, schupp}@tu-harburg.de|%
\urldef{\mailsb}\path|stephan.weissleder@gmail.com|%


\title[Automated Generation of Test Data using AMPL]{Automated Generation of
Test Data using AMPL}
%\subtitle[M.Sc. Thesis]{A Master Thesis} 
\author[Kurth \& Schupp \& Wei{\ss}leder]{%
\underline{Felix Kurth}%
\and Sibylle Schupp%
\and Stephan Wei{\ss}leder%
}%
\institute{Hamburg University of Technology, Institute for Software Systems,\\%
Schwarzenbergstr. 95, 21073 Hamburg, Germany\\%
\mailsa\\%
\url{http://www.sts.tu-harburg.de}
\and
\mailsb\\
\url{www.model-based-testing.de/person/stephan_weissleder}}%


\institute[sts.tuhh.de]
{
 Institute for Software Systems\\ Hamburg University of Technology\\
 Schwarzenbergstr. 95, 21073 Hamburg, Germany\\
 }

\day=25
\month=7
\year=2014
\date[TAP2014]{8th International Conference on Tests \& Proofs\\
\today
} 

\pgfdeclareimage[height=1.2cm]{STS-logo}{STS-logo}
\logo{\pgfuseimage{STS-logo}}
\subject{Generating Test Data from a UML Activity using the AMPL Interface for Constraint Solvers}

\begin{document}

\begin{frame}
\titlepage
\end{frame}

\begin{frame}
\frametitle{Reuse Control Flow Information from Activity Diagrams for Test Generation}
\includegraphics[width=\textwidth]{pics/IntroductoryImage.pdf}
\end{frame}

\begin{frame}
\frametitle{Outline}
\tableofcontents
\end{frame}

\section{Introduction}

\begin{frame}
\frametitle{Overview}
\includegraphics[width=\textwidth]{pics/SimplifiedWorkflow.pdf}
\end{frame}

\begin{frame}
\frametitle{Overview}
\begin{block}{Algorithm}
\begin{itemize}
\item Symbolic Execution
\item Constraint Solving
\item Early Infeasible Path Elimination
\item Boundary Value Analysis
\end{itemize}
\end{block}
\begin{block}{Results}
\begin{itemize}
\item Extremly high mutation scores for demo models
\item Experimental parameter tweaking
\end{itemize}
\end{block}
\end{frame}

\section{The Algorithm}
\begin{frame}
\frametitle{Outline} \tableofcontents[currentsection]
\end{frame}

\subsection{AMPL Modelling}
\begin{frame}
\frametitle{AMPL Modelling}
\begin{itemize}
  \item AMPL is a common interface to a variety of industry--strength constraint
  solvers.
  \item Source--to--source translation of UML Activity into AMPL model.
  \item Control--flow path is specified as AMPL data.
  \item Solution of an AMPL program (model + data) contains test data for a
  certain control--flow path.
\end{itemize}
\begin{block}{Supported Solvers} 
Cplex, LPSolve, Couenne, GeCoDE, ILOGCP, Minos, Gurobi, GLPK, Bonmin, Ipopt,
Xpress, \ldots
\end{block}
\begin{block}{Supported Constraint Types}
linear, non--linear, integer, mixed--integer, logical, \ldots
\end{block} 
\end{frame}

\begin{frame}[fragile]
\frametitle{Basic Example}
\begin{columns}
 \column{.39\textwidth} \ 
	\begin{block}{Activity Diagram} 
	\def\svgwidth{\textwidth}
	\scriptsize
	\import{pics/}{BasicExamples.pdf_tex}
	\end{block} 
\column{.56\textwidth} \ 
	\begin{block}{AMPL Model} 
		\begin{lstlisting}[basicstyle=\ttfamily\scriptsize,language=ampl]
param n; # Amount of executed Actions

# Variables (Property or Parameter)
var x{0..n} : integer := 1;
var y : integer := 1;

# Postconditions
set t within {0..n} default {};
s.t. t_post0{i in t} : (y)=(x[i-1]);
s.t. t_post1{i in t} : (x[i])=(x[i-1]);
set e within {0..n} default {};
s.t. e_post0{i in e} : (y)=(x[i-1]-100);
s.t. e_post0{i in e} : (x[i])=(x[i-1]);

# Guards
set d2e within {0..n} default {};
s.t. d2e_g{i in d2e} : (x[i])>=(6.0);
set d2t within {0..n} default {};
s.t. d2t_g{i in d2t} : (x[i])<=(5.0);
\end{lstlisting}
	\end{block} 
\end{columns}
\end{frame}

\subsection{Early Infeasible Path Elimination}
\begin{frame}
\frametitle{Early Infeasible Path Elimination}
	\begin{columns}[c]
		\column[c]{0.4\textwidth}
			\includegraphics[width=\textwidth]{./pics/VennTree.pdf}
		\column{0.6\textwidth}
				\begin{itemize}
\item Prune control--flow paths for which no test data exist from path
search.
% \item Determine test scenarios fulfilling model structure based
% coverage criteria efficiently.
\item To ensure termination activity diagram is unrolled up to a maximum path
length.
\item If AMPL program for a sub--path is infeasible no extension of that
path can be feasible.
\item unchecked steps provide trade--of between early infeasible path
elimination and unnecessary solver invocations.
				\end{itemize}
	\end{columns}
\end{frame}

\subsection{Boundary Value Analysis}
\begin{frame}
\frametitle{Boundary Value Analysis}
\begin{columns}[c]
\column[c]{0.3\textwidth}
	\includegraphics[width=\textwidth]{./pics/BVA.pdf}
\column{0.7\textwidth}
	\begin{itemize}
\item For a certain path constraint solvers will find any test data fulfilling
all path constraints.
\item Test data at the boundary of path constraints are most likely to trigger
an error.
\item Boundary value analysis is possible by adding a linear objective function
to the AMPL model.
	\end{itemize}
\end{columns}
\end{frame}

\section{Industrial Case Study}
\begin{frame}
\frametitle{Outline} \tableofcontents[currentsection]
\end{frame}

\begin{frame}
\frametitle{Industrial Case Study (mixed integer linear)}
\begin{itemize}
  \item The Original Model
\begin{itemize}
  \item Activity diagram consists of 21 \UMLType{Action}s, 24
  \UMLType{ControlNode}s and two nested \UMLType{LoopNode}s 
  \item C code snippets are embedded
\end{itemize}
\item Manual Adaptations
  \begin{itemize}
  \item All variables and C structs are represented by several \UMLType{Property} elements
  \item OCL constraints are deduced with an educated guess from the embedded C code snippets
  \item Hierarchical \UMLType{LoopNode}s are flattened
\end{itemize}
\end{itemize}
\begin{block}{}
The resulting constraint satisfaction problem is a mixed integer linear program
\end{block}
\end{frame}

\begin{frame}
%\frametitle{Runtime Depending on the Unchecked Steps}
\begin{tikzpicture}
\begin{axis}[
width=0.6\textwidth,
height=\textheight*0.8,
legend style={legend columns=1,at={(1.02,0.98)},anchor=north west},
xlabel={unchecked steps},
xmax=15,
ylabel={runtime $[s]$},
yticklabels={{$1$},{$10$},{$100$},{$10^3$},{$10^4$},{$10^5$}},
extra y ticks={3.6e12,2.592e14},
extra y tick labels={{1h},{3d}},
extra tick style={
        major grid style=black,
        tick align=outside,
        tick style=black
    },
minor x tick num=1,
ymajorgrids=true,
yminorgrids=true,
xmajorgrids=true,
xminorgrids=true,
ymode=log,
]
\addlegendimage{empty legend}
\addlegendentry{maximum path length}
\addplot[densely dashed, blue] table[x=PATHSEARCH_UNCHECKED_STEPS,y=time(ns)]{../Thesis/Experiment-DATA/CaseStudyUncheckedSteps90.csv};
\addlegendentry{90};
\addplot[densely dashed, green] table[x=PATHSEARCH_UNCHECKED_STEPS,y=time(ns)]{../Thesis/Experiment-DATA/CaseStudyUncheckedSteps80.csv};
\addlegendentry{80};
\addplot[densely dashed, red] table[x=PATHSEARCH_UNCHECKED_STEPS,y=time(ns);]{../Thesis/Experiment-DATA/CaseStudyUncheckedSteps70.csv};
\addlegendentry{70};
\addplot[blue] table[x=PATHSEARCH_UNCHECKED_STEPS,y=time(ns);]{../Thesis/Experiment-DATA/CaseStudyUncheckedSteps60.csv};
\addlegendentry{60};
\addplot[green] table[x=PATHSEARCH_UNCHECKED_STEPS,y=time(ns)]{../Thesis/Experiment-DATA/CaseStudyUncheckedSteps50.csv};
\addlegendentry{50};
\addplot[red] table[x=PATHSEARCH_UNCHECKED_STEPS,y={time(ns)}]{../Thesis/Experiment-DATA/CaseStudyUncheckedSteps40.csv};
\addlegendentry{40};
\end{axis}
\end{tikzpicture}
\begin{block}{}
For a maximum path length of 90, early infeasible path elimination reduces the
runtime from 3 days to less than 1 hour.
\end{block}
\end{frame}

\begin{frame}
%\frametitle{Runtime for Different Solvers}
\begin{tikzpicture}
\begin{axis}[
width=0.59\textwidth,
height=\textheight*0.8,
%legend columns=-1,
%legend to name=solvers,
legend style={at={(0.02,0.98)},anchor=north west},
xlabel={maximum path length},
ylabel={time $[s]$},
yticklabels={0,{$1$},{$10$},{$100$},{$10^3$},{$10^4$},{$10^5$}},
extra y ticks={3.6e12,2.592e14},
extra y tick labels={{1h},{3d}},
extra tick style={
        major grid style=black,
        tick align=outside,
        tick style=black
    },
minor x tick num=1,
xmin=15,
xmax=115,
ymax=1e14,
ymajorgrids=true,
yminorgrids=true,
xmajorgrids=true,
xminorgrids=true,
ymode=log,
]
\addplot[green] table[x=PATHSEARCH_MAX_PATHLENGTH,y=time(ns)] {../Thesis/Experiment-DATA/CaseStudyRuntimeCplex.csv};
\addlegendentry{Cplex};
\addplot[blue] table[x=PATHSEARCH_MAX_PATHLENGTH,y=time(ns)] {../Thesis/Experiment-DATA/CaseStudyRuntimeLPSolve.csv};
\addlegendentry{LPsolve};
\addplot[orange] table[x=PATHSEARCH_MAX_PATHLENGTH,y=time(ns)] {../Thesis/Experiment-DATA/CaseStudyRuntimeCouenne.csv};
\addlegendentry{Couenne};
\addplot[red] table[x=PATHSEARCH_MAX_PATHLENGTH,y=time(ns)] {../Thesis/Experiment-DATA/CaseStudyRuntimeGecode.csv};
\addlegendentry{GeCoDE};
\addplot[dashed] expression[no markers, domain=30:110]{2e7*1.12^(x)} node[pos=0.5,sloped,fill=white, below, opacity=1,text opacity=1] {$1.12 ^ {x}$} ;
\end{axis}
\end{tikzpicture}%
\begin{tikzpicture}
\begin{axis}[
width=0.39\textwidth,
height=\textheight*0.8,
ylabel={number of test cases},
xlabel={maximum path length},
minor x tick num=4,
ymajorgrids=true,
yminorgrids=true,
xmajorgrids=true,
xminorgrids=true,
ymode=log,
]
\addplot[blue] table[x=PATHSEARCH_MAX_PATHLENGTH,y=PathsFound]{../Thesis/Experiment-DATA/CaseStudyRuntimeLPSolve.csv};
\addplot[color=black, style=dashed] expression[no markers, domain=30:100]{1.1 ^ (x)} 
node[pos=0.5,sloped,fill=white, below, opacity=1,text opacity=1] {$1.1 ^ {x}$}
;
\end{axis}
\end{tikzpicture}
\begin{block}{}
LPsolve solved 12,849,881 mixed integer linear programming instances in 13 hours
to produce 83,000 test cases. Couenne is slower since it is optimized for mixed
integer non--linear programming
\end{block}
\end{frame}

\begin{frame}
%\frametitle{Runtime with and without Boundary Value Analysis}
\begin{tikzpicture}
\begin{axis}[
width=\textwidth,
height=0.8\textheight,
%title={Influence of boundary value analysis},
legend style={at={(0.02,0.98)},anchor=north west},
ylabel={time $[s]$},
xlabel={maximum path length},
%ytick={1e8,1e10,1e12,1e14},
yticklabels={0,{1},{10},{100},{$10^3$},{$10^4$},{$10^5$}},
extra y ticks={3.6e12,2.592e14},
extra y tick labels={{1h},{3d}},
extra tick style={
        major grid style=black,
        tick align=outside,
        tick style=black
    },
ymajorgrids=true,
yminorgrids=true,
xmajorgrids=true,
xminorgrids=true,
ymode=log,
]
\addplot[blue] table[x=PATHSEARCH_MAX_PATHLENGTH,y=time(ns)]{../Thesis/Experiment-DATA/CaseStudyRuntimeBoundaryValues.csv};
\addlegendentry{with boundary value analysis};
\addplot[red] table[x=PATHSEARCH_MAX_PATHLENGTH,y=time(ns)]{../Thesis/Experiment-DATA/CaseStudyRuntimeNoBoundaryValues.csv};
\addlegendentry{without boundary value analysis}
\end{axis}
\end{tikzpicture}%
\begin{block}{}
For a maximum path length of 70 boundary value analysis imposes extra work for
only 4.4\% of all solver invocations. This reduces to 1.1\% for a maximum path
length of 100.
\end{block}
\end{frame}

\section{Summary \& Outlook}

\begin{frame}
\frametitle{Summary}
\begin{itemize}
  \item Current constraint solvers can efficiently generate test data for
  industry scale applications.
  \item Mixed integer linear programming can be handled highly efficient.
  \item Test generation for models with mixed integer non-linear constraints is
  possible but time consuming.
  \item Early infeasible path recognition with 2 unchecked steps drastically
  reduces the runtime.
  \item Boundary value analysis can be performed with almost no effort.
  \item The ActivityTester (AcT) tool is available at
  \href{http://parteg.sourceforge.net/}{http://parteg.sourceforge.net/}.
\end{itemize}
\end{frame}

\begin{frame}
\frametitle{Outlook}
\begin{itemize}
  \item Add support for further UML/OCL modelling elements and features e.g.
  \UMLType{CallBehaviourAction} and complex data types.
  \item Reuse test goal management from ParTeG to support feasible coverage
  criteria instead of all control flow paths.
\end{itemize}
\end{frame}

\section{Demonstration \& Questions}
\begin{frame}
\begin{block}{}
\begin{center}
\Huge{Demonstration}
\end{center}
\end{block}
\end{frame}


\begin{frame}
\begin{block}{Thank you!}
\begin{center}
\Huge{Questions?}
\end{center}
\end{block}
\end{frame}

\input{appendix.tex}

\end{document}
